package com.example.demo.arithmetic.datastructure.tree;

/**
 * 自平衡二叉树实现之一
 * <p>
 * 对于所有的节点 如果左右子树 高度差不超过1
 * <p>
 * 失去平衡的几种情况
 */
public class AVLTree {

    // 求节点高度
    public int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    public AVLNode rightRotate(AVLNode node) {
        AVLNode left = node.left;
        AVLNode right = left.right;
        node.left = right;
        left.right = node;
        return left;
    }

    public AVLNode leftRotate(AVLNode node) {
        AVLNode right = node.right;
        AVLNode left = right.left;
        right.left = node;
        node.right = left;
        return left;
    }

    private void updateHeight(AVLNode node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    // 平衡因子 左右子树高度差 <=1 平衡
    // >1左高
    // <-1 右高
    // 0左右一样高
    private int bf(AVLNode node) {
        return /*Math.abs*/(height(node.left) - height(node.right));
    }

    //    public int maxHeight(AVLNode node) {
    //        if (node == null) {
    //            return 0;
    //        }
    //
    //
    //        int maxLeft = maxHeight(node.left);
    //        int maxRight = maxHeight(node.right);
    //        return Math.max(maxLeft, maxRight) + 1;
    //    }


    static class AVLNode {
        int key;
        Object val;
        AVLNode left;
        AVLNode right;
        /**
         * 高度
         */
        int height = 1;

        public AVLNode(int key, Object val) {
            this.key = key;
            this.val = val;
        }

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object val, AVLNode left, AVLNode right) {
            this.key = key;
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}



